package leetcode.code0854;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution3 implements IDebug {

	int limit;
	char[] cs1, cs2;
	int p;

	public int kSimilarity(String s1, String s2) {
		int len = s1.length();
		cs1 = new char[len];
		cs2 = new char[len];
		p = 0;
		for (int i = 0; i < len; i++) {
			if (s1.charAt(i) != s2.charAt(i)) {
				cs1[p] = s1.charAt(i);
				cs2[p] = s2.charAt(i);
				p++;
			}
		}
		limit = 1 << p;
		Integer[][] dp = new Integer[limit][p];
		return this.f(0, dp, 0);
	}

	private int f(int cur, Integer[][] dp, int k) {
		if (cur == limit - 1) {
			return 0;
		}
		if (dp[cur][k] != null) {
			return dp[cur][k];
		}
		int ans = 20;
		for (int i = 0; i < p; i++) {
			if ((cur & (1 << i)) == 0) {
				for (int j = i + 1; j < p; j++) {
					if (((cur & (1 << j)) == 0) && cs2[i] == cs1[j]) {
						int tmp = cur | (1 << i);
						if (cs1[i] == cs2[j]) {
							tmp |= (1 << j);
						}
						this.swap(cs1, i, j);
						ans = Math.min(ans, this.f(tmp, dp, k + 1) + 1);
						this.swap(cs1, i, j);
					}
				}
			}
		}
		dp[cur][k] = ans;
		return ans;
	}

	private void swap(char[] cs, int i, int j) {
		char c = cs[i];
		cs[i] = cs[j];
		cs[j] = c;
	}

	@Override
	public void debug4() {
		H.compare(10, this.kSimilarity("fffeaacbdbdafcfbbafb", "abcbdfafffefabdbbafc"));
		H.compare(2, this.kSimilarity("abcde", "ebdca"));
		H.compare(9, this.kSimilarity("aaaabbbbccccddddeeee", "edcbaacbcebcdbeedaad"));
		H.compare(9, this.kSimilarity("abccaacceecdeea", "bcaacceeccdeaae"));
		H.compare(6, this.kSimilarity("aabbccddee", "cdacbeebad"));
		H.compare(9, this.kSimilarity("abcabcdefabcdef", "faebacbbdafdecc"));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
